package second.codeTop.package1;

/**
 * @ClassName LC53
 * @description: 最大子数组和
 * @author: 荣燊
 * @create: 2022-03-07 11:01
 **/
public class LC53 {
    public static void main(String[] args) {

    }

    // df[i] = Math.max{df[i-1]+nums[i], nums[i]}
    // 还需要保存一个max
    public static int maxSubArray(int[] nums) {
        int pre = nums[0];
        int max = nums[0];
        for (int i=1; i<nums.length; i++) {
            pre = Math.max(pre+nums[i], nums[i]);
            max = Math.max(max, pre);
        }
        return max;
    }
}
